First-In First-Out memories (FIFOs) are used in a variety of applications. For example, they can be used in electronic circuits for buffering data transferred between a pair of circuits that operate at different clock rates, for example, ATMs, or between different processing stages. Generally, there are two types of FIFOs, a shifting (also called latch) based FIFOs and memory-based FIFOs. The shifting based FIFO is the shift register type that uses a self-clocking register for shifting data from a write port to a read port. The memory-based FIFO utilizes a Random Access Memory (RAM) as its storage element, rather than a shift register. The RAM within the RAM-type FIFO may have a single (combined) read/write port or separate (dual) ports for reading and writing data. The RAM further includes n storage rows or words, where n is an integer. One type of dual-port RAM-type FIFO uses a ring-type addressing mechanism. Register type FIFOs include either a shared read/write port or separate read and write ports. Such FIFOs also include a Write Address Register (WAR) connected to the write port and a Read Address Register (RAR) connected to the read port. The WAR and RAR operate to address the RAM. The WAR and RAR address the RAM so that words of data can be written to or read from the RAM. In addition, during normal operation of the FIFO, as a result of a read or write operation on a given memory location of the RAM, the FIFO causes the RAR or WAR to be incremented to address the next successive memory location (also called an address) in the RAM. Moreover, the input port of the RAM is connected to a Data Input Register (DIR) that acts as a buffer to temporarily store incoming data supplied on a Data Input (DI) line before such data is written to the RAM. Similarly, the output port of the RAM is connected to a Data Output Register (DOR) that stores data read from the RAM. Also, the FIFO has reset and re-transmit functions. The reset function causes both address registers to be positioned at the first memory location of the FIFO's memory. The re-transmit function causes only the read address register to be positioned at the first memory location of the FIFO's memory while not changing the write address register's position.
From a reliability standpoint, it is desirable to test all aspects of the FIFO. Fault models and algorithms have been described in the literature for detecting faults in RAMs. In addition, U.S. Pat. No. 5,513,318 (the '318 patent) to Ad J. van de Goor and Yervant Zorian, provides a technique to detect memory, addressing and functional faults that may occur in a ring-address FIFO. The disclosure of that patent is incorporated herein in its entirety by reference.
Such algorithms (including the '318 patent algorithm) detect a predetermined number and type of faults in a fault model. In addition, the comprehensiveness of each fault detected is a consideration in designing the algorithms. Comprehensiveness is exemplified by the algorithm testing for a particular fault type solely when the write and read address pointers are positioned at a single or a limited number of memory locations versus detecting such fault for a greater number of words in the FIFO memory. However, comprehensiveness impacts the length of time it takes for the algorithm to execute or run. For example, the testing time to detect a particular fault type for each of n words would be longer than such time to test it from a single or a limited number of n words. Accordingly, there is a determination of comprehensiveness and testing time built into the algorithms.
The testing time for a series of operations in an algorithm or the entire algorithm is defined in part by the number of operations per address multiplied by the total number of distinct addresses in the memory array on which the operations are executed. Therefore, the testing time can be reduced by reducing the number of operations or the number of distinct addresses on which such operations execute.
There is a need to improve the testing time for portions of algorithms (e.g., the '318 patent algorithm) which test particular operations, such as, for example, the reset, re-transmit and the memory cells. In addition, there is a need to improve the comprehensiveness of the faults detected by such algorithms.
In addition, in order for the '318 patent algorithm to detect the fault model described in that patent, it should be applied to ring-address FIFO. If it is applied to more general memory-based FIFOs, then that fault coverage (or the number of fault types detected) is reduced. For example, the '318 patent algorithm may not detect faults involving the manner in which the read and write pointers address the FIFO memory (called addressing faults). Accordingly, there is a need for a method of detecting a fault model, including at least addressing faults, for memory-based FIFOs besides ring address FIFOs.
Our invention is a method and apparatus for testing all types of memory-based FIFOs, including shift register or single or dual port RAM-type memories or ring-type addressing mechanisms, in order to detect faults, including addressing faults.
In one embodiment of our invention, the method and apparatus cause the FIFO to execute several steps of operations, including read, write, reset and re-transmit operations. In addition, during particular operations, a write enable signal, a read enable signal or a data input line for writing data to the RAM are held at constant binary values. In addition, one object of the present invention is to improve the testing time or comprehensiveness of fault detection for testing the reset, re-transmit or memory cell operations. Also, it is another object of the present invention to detect faults corresponding to a fault model, including addressing faults, for all types of memory-based FIFOs.
When executed, an initial step of operations generally checks basic operations of the FIFO and also detects faults associated with over-read protection, write acknowledge and read acknowledge, write enable, read enable and re-transmit. A first step of operations can next be executed according to the present invention.
The first step of operations, when executed, generally checks the reset operation. The testing time for this first step of operations (or amount of time for the test to complete) is proportional to n*log(n). Since the testing time for the '318 patent FIG. 3 algorithm (steps 9 to 13) is proportional to n.sup.2, the testing time for the present invention is shorter than the testing time for the '318 patent algorithm for checking the reset function. This is because in the present invention, the reset operation is checked for each binary address where the address contains a single binary one value bit while the remaining bits in the address contain binary zero values. For example, the present invention checks the reset function from the addresses 000 . . . 001, 000 . . . 010, 000 . . . 100 et seq. 010 . . . 000 to 100 . . . 000. In contrast, the '318 patent algorithm checks the reset function from each of the n words in the FIFO memory. Also, the present invention method checks for over-read protection in connection with this first step of operations. Such fault may not be detected during the reset function checking in the '318 patent. Therefore, in addition to the general function of checking the reset operation, the first step of operations detects faults associated with empty-FIFO (indicated by a empty-FIFO flag), full-FIFO (indicated by a full-FIFO flag), addressing faults, write acknowledge and over-write protection.
Next, the present invention can involve the execution of a second step of operations. When executed, the second step of operations generally checks the re-transmit operations of the FIFO. The second step of operations is implemented on the same binary addresses as in the first step of operations. The '318 patent FIG. 3 algorithm (step 16) tests the re-transmit function from a single address. Therefore, the present invention checks for re-transmit faults more comprehensively than the '318 patent algorithm. In addition, the second step of operations also detects over-read protection. All such faults may not be detected during the re-transmit function checking in the '318 patent. Therefore, in addition to the general function of checking the re-transmit, the second step of operations detects faults associated with empty-FIFO, over-read protection and read acknowledge.
A third step of operations can next be executed according to the present invention. When executed, the third step of operations resets the FIFO in order to support detection of faults during subsequent steps of operations. A fourth step of operations which initializes the memory cells of the FIFO is executed next. The fourth step detects faults associated with reset and full-FIFO.
Next is a fifth step of operations, which generally checks the memory cells of the FIFO memory. The fifth step of operations involves writing binary zero values into the entire FIFO memory followed by writing a binary one value to a single memory location. Then, each memory location containing a binary zero value is read and verified and the memory location containing the binary one value is read and verified to ensure that the values have been retained. During each read operation, the data input line is maintained at a constant value opposite to the binary value of the word being read. After the read operation of the binary one value, binary zero values are written to the entire array in order to reinitiate the memory and position the WAR at the correct memory location. This is repeated for each of the n words in memory. In this way, the fifth step of operations detects faults for a given memory cell or word due to a transition in the binary value of another cell or word (called coupling faults). This includes coupling faults caused by neighboring memory cells within a single word as well as neighboring memory cells between neighboring words. The '318 patent FIG. 3 algorithm steps 14 to 22 detects solely faults caused by neighboring memory cells within a single word, and only a subset of those between neighboring words. Therefore, the present invention checks for memory cell operations more comprehensively than the '318 patent algorithm. In addition to coupling faults, the fifth set of operations detects faults associated with stuck-at-faults, full-FIFO, read disturb and transition faults.
Next, sixth and seventh steps of operations, which reset and initialize the FIFO, respectively, support detection of faults during subsequent steps of operations. The eighth step of operations is executed next. The eighth step also generally checks the memory cells of the FIFO memory and detects the same types of faults as the fifth set of faults, except that in the eighth step, faults are detected by operations (e.g., read and write) involving binary values which are the complements of the binary values used during the fifth step.
The ninth and tenth steps of operations can next be executed according to the present invention. When executed, the ninth and tenth steps of operations generally check for data retention faults in the FIFO memory cells and detect faults associated with data retention. The difference between the ninth and tenth steps is that the data retention faults are identified for a particular binary value in the ninth step while such faults are detected for the complement of such binary value in the tenth step.